from common import *
import sys
import math


# Job size
job_size = 42000


def format_factor(base, exponent):
    if exponent > 1:
        return "%s**%s"%(base, exponent)
    return str(base)

def PrimeFacControllerFunc(numberIn, workerIn, resultOut, workerOut):

    while True:
    
        factors = {}
        num = numberIn()
        orig = num
        w = 1
        activeWorkerList = []
        prepareWorkers = 1

        # we take advantage of the fact that (i+1)**2 = i**2 + 2*i +1
        i = 2
        sqi = long(math.pow(i,2))
        if (sqi <= num):
            while True:
                # Fetch result or init
                (w_id, factor_array) = workerIn()
                    
                if w_id in activeWorkerList:
                    del activeWorkerList[activeWorkerList.index(w_id)]
                    
                #else:
                    #print "NOT FOUND ID", w_id

                # If any factors have been found, then get results from all workers.
                if (len(factor_array)):
                    wList = activeWorkerList[:]
                    
                    j = 0
                    for c in wList:
                        valid_c_w_id = False
                        while (not valid_c_w_id):
                            (c_w_id, c_factor_array) = workerIn()
                            j += 1
                            if c_w_id in activeWorkerList:
                                valid_c_w_id = True
                                del activeWorkerList[activeWorkerList.index(c_w_id)]
                            

                        #print c_w_id
                        if (len(c_factor_array) and c_factor_array[0] < factor_array[0]):
                            # This worker produced a better result
                            factor_array = c_factor_array

                    # send empty jobs to workers
                    for c in range(j):
                        workerOut((-c,(num, i, 0)))

                    # Reset to next working unit
                    i = ((factor_array[0] / job_size)+1)*job_size
                    sqi = long(math.pow(i,2))                    

                for factor in factor_array:
                    num /= long(factor)
                    factors[factor] = factors.get(factor, 0) + 1

                if (sqi > num and len(activeWorkerList) == 0):
                    #print "SHUTDOWN"
                    # Shutdown, all results has been received

                    # Prepare workers in use
                    #print "prepareWorkers", prepareWorkers
                    for x in range(prepareWorkers):
                        #print "preparing", x
                        workerOut((-x,(num, i, 0)))

                    break
                    
                    #while w:
                    #    workerOut((num, i, 0))
                    #    w -= 1


                if (sqi <= num):
                    # Send new job
                    workerOut((w,(num, i, job_size)))
                    activeWorkerList.append(w)

                    w += 1
                    i += job_size
                    sqi = long(math.pow(i,2))

                else:
                    # Add to the amount of workers, that has been in use
                    # and is to be ready, if prime factorization is repeated
                    # for another number
                    prepareWorkers += 1

                #print "Active workers", str(activeWorkerList)


        #print "LOOP DONE"   
        print "Number of jobs done:", w

        if num not in (1, orig):
            factors[num] = factors.get(num, 0) + 1

        # Checking primes (HACK to fix that we might get bogus results from the workers)
        for f in factors.copy():
            for check_prime in factors.copy():
                if (check_prime != 0 and f != check_prime and (f%check_prime) == 0):
                    if factors.has_key(f):
                        print "REMOVED",f
                        del factors[f]
                    #factors[f] = factors.get(f, 1) - 1
                        
        out = [format_factor(base, exponent)
               for base, exponent in sorted(factors.items())]

        resultOut(out)
    
